Heap ヒープ
以下のルールを満たす二分木 Binary Treeのデータ構造 Data Structure
親ノード Nodeの値は子ノードの値以上
木のノード番号が一番大きいノードより若い番号のノードはすべて存在
ノード Nodeの親子関係
ノード k の子供は、2k+1,2k+2
ノード k の親は、(k−1)/2 (余りは切り捨て)
特徴
table:heap
処理内容 計算時間 備考
配列に値 v を追加 O(log n) 追加してもヒープ状態を保つ
配列から最大値を削除 O(log n) ルートを消して木を整える
配列内の最大値を知る O(1) 二分木のルート (ノード 0) 値
利点
データ数に関係なくO(1)で取り出すこと可能
常にroot 根に最大値(最小値)が格納されているため
欠点
データの追加、取り出しをした場合
再構築必要
TODO:実装がまだちゃんとできてない
💯ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
特徴の説明がわかりやすい！！
例
2349. Design a Number Container System解いたときのチャット